import java.util.BitSet;

/**
 * 获取所有质数
 * 时间要求: t < 2s(考虑到CPU性能)
 * 数据要求: 0 < n < 100 000 000
 */
public class Demo1 {

    private static final int N = 100000000;

    public static void main(String[] args) {
        Long start = System.currentTimeMillis();

        BitSet bitSet = new BitSet(N);// 默认全为false
        double len = Math.sqrt(N);
        for (int i = 2; i < len; i++)
            if (!bitSet.get(i))
                for (int j = i * i; j < N; j += i)
                    bitSet.set(j);

        Long end = System.currentTimeMillis();
        System.out.println(end - start + " ms");

        for (int i = 2; i < 100; i++)
            if (!bitSet.get(i))
                System.out.println(i);
    }
}
